package leetcode.code1049;

import java.util.Arrays;

public class Solution2 {
	public int lastStoneWeightII(int[] stones) {
		int max = 0;
		for (int i = 0; i < stones.length; i++) {
			max = Math.max(max, stones[i]);
		}
		int size = (max << 1) + 1;
		boolean[] exists = new boolean[size];
		exists[stones[0] + max] = true;
		exists[max - stones[0]] = true;
		for (int i = 1; i < stones.length; i++) {
			int stone = stones[i];
			boolean[] add = new boolean[size];
			for (int j = 0; j < size; j++) {
				if (exists[j]) {
					if (j + stone < size)
						add[j + stone] = true;
					if (j - stone >= 0)
						add[j - stone] = true;
				}
			}
			exists = add;
		}
		int ans = 0;
		for (int i = 0; i < exists.length; i++) {
			if (exists[i] && Math.abs(i - max) < Math.abs(ans - max)) {
				ans = i;
			}
		}
		return Math.abs(ans - max);
	}
}
